#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<Mesh_IO/Mesh_IO.h>


#include<Mesh/libcell_iterator.h>
#include<tool/libcell_tools_kd_node.h>
#define quote lib_cell_quote


#include<libcell_macros.h>

void  quick_sort(int*shu,int left,int right);  
static inline void swap(int *shu,int left,int right)  
{  
    int temp;  
    temp = shu[left];  
    shu[left] = shu[right];  
    shu[right] = temp;  
} 

static inline void my_swap(template_v** values,int left,int right)
{
    template_v* temp=values[left];
    values[left]=values[right];
    values[right]=temp;
}
static void my_sort_vertex(template_v** values,int left,int right,int dim)
{
    if(left>=right)
    {
        return;
    }
    int m,d=dim;  
    //int d=dim%values[0]->point_size;
    m = left;  
    for (int i=left+1;i<=right;i++)
    {
        if(values[i]->point[d]<values[left]->point[d])  
        { 
            my_swap(values,++m,i);
        }  
    }   
    my_swap(values,left,m);  
    my_sort_vertex(values,left,m-1,d);  
    my_sort_vertex(values,m+1,right,d);
} 
int my_compare(const void* v1,const void* v2)
{
    return (int)(((template_v*)(v1))->point[0]-((template_v*)(v2))->point[0]);
}

void my_test1()
{

    Mesh mesh;
    Mesh_init(&mesh);
    _ReadOff_(&mesh,"0831.off",3);
    int len=mesh.num_v(&mesh);
    template_v** values=(template_v**)malloc(sizeof(template_v*)*len);
    int i=0;
    for(auto vit=mesh.v_begin(&mesh);vit!=mesh.v_end(&mesh);vit++)
    {
        values[i]=(template_v*)(quote(vit)); 
        i++;
    } 
    //create_kd_tree(values,len,0);
    int d=0;
    //len=50000;
    //qsort(values,len-1,sizeof(template_v*),my_compare);
    my_sort_vertex(values,0,len-1,d);  
    printf("num v:%d\n",len);

    for (int i=0;i<len-1;i++)  
    {
        if (values[i]->point[d]>values[i+1]->point[d])  
        {
            printf("%d %d\n",values[i]->point[d],values[i+1]->point[d]);  
        } 
    }


}

void my_test()
{
    clock_t start, finish;  
    double duration;  
    srand((unsigned)time(NULL));
    int len=1000000;
    int *shu=(int*)malloc(sizeof(int)*len);
    for(int i=0;i<len;i++)
    {
        shu[i]=rand()%5000000;
    }
    printf ("len:%d \n",len);  
    start = clock();  
    quick_sort(shu,0,len-1);  
    finish = clock();  
    duration = (double)(finish - start) / CLOCKS_PER_SEC;  
    printf ("duration: %.6f\n",duration);  
    for (int i=0;i<len-1;i++)  
    {
        if (shu[i]>shu[i+1])  
        {
            printf("%d %d\n",shu[i],shu[i+1]);  
        }
        // if(i<1000)
        // {
        //     printf("%d ",shu[i]);
        // }
    }
}

int main()  
{ 
    my_test1(); 

    my_test();

  
    return 0;    
}  
  

  
void quick_sort(int*shu,int left,int right)  
{  
    int m;  
    if (left>=right)  
    {
        return;  
    }
    m = left;  
    for (int i=left+1;i<=right;i++)
    {
        if (shu[i]<shu[left])  
        {swap(shu,++m,i);
        }  
    }   
    swap(shu,left,m);  
    quick_sort(shu,left,m-1);  
    quick_sort(shu,m+1,right);  
}  
  

